{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the K-Sum of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出数组的第 K 大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个 <strong>正</strong> 整数 <code>k</code> 。你可以选择数组的任一 <strong>子序列</strong> 并且对其全部元素求和。</p>\n",
    "\n",
    "<p>数组的 <strong>第 k 大和</strong> 定义为：可以获得的第 <code>k</code> 个 <strong>最大</strong> 子序列和（子序列和允许出现重复）</p>\n",
    "\n",
    "<p>返回数组的 <strong>第 k 大和</strong> 。</p>\n",
    "\n",
    "<p>子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。</p>\n",
    "\n",
    "<p><strong>注意：</strong>空子序列的和视作 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,4,-2], k = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>所有可能获得的子序列和列出如下，按递减顺序排列：\n",
    "- 6、4、4、2、<strong><em>2</em></strong>、0、0、-2\n",
    "数组的第 5 大和是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,-2,3,4,-10,12], k = 16\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>数组的第 16 大和是 10 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= min(2000, 2<sup>n</sup>)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-k-sum-of-an-array](https://leetcode.cn/problems/find-the-k-sum-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-k-sum-of-an-array](https://leetcode.cn/problems/find-the-k-sum-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,-2]\\n5', '[1,-2,3,4,-10,12]\\n16']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "                n = len(nums)\n",
    "            \n",
    "                tot = 0\n",
    "                for i,x in enumerate(nums):\n",
    "                    if x >= 0:tot += x\n",
    "                    else:nums[i] = -x\n",
    "                nums.sort()\n",
    "                h = [[0,0]]\n",
    "                while k > 1:\n",
    "                    s,i = heappop(h)\n",
    "                    if i < n:\n",
    "                        heappush(h,[s + nums[i],i+1])\n",
    "                        if i:heappush(h,[s+nums[i] - nums[i-1],i+1])\n",
    "                    k -= 1\n",
    "                return tot - h[0][0]\n",
    "                            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        s0 = sum(x for x in nums if x > 0)\n",
    "        a = [abs(x) for x in nums]\n",
    "        a = nsmallest(k, a)\n",
    "        a.reverse()\n",
    "        n = len(a)\n",
    "        q = []\n",
    "        s = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal s\n",
    "            if i == n:\n",
    "                # 存入负数，最小堆当最大堆用\n",
    "                heappush(q, -s)\n",
    "                # 限制 q 为最多 k 个\n",
    "                if len(q) > k: heappop(q)\n",
    "                return\n",
    "\n",
    "            # 剪枝\n",
    "            if len(q) == k and s >= -q[0]: return\n",
    "\n",
    "            # 不取 a[i]\n",
    "            dfs(i + 1)\n",
    "\n",
    "            # 取 a[i]\n",
    "            s += a[i]\n",
    "            dfs(i + 1)\n",
    "            s -= a[i]\n",
    "\n",
    "        dfs(0)\n",
    "        return s0 - (-q[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        greater = [each for each in nums if each > 0]\n",
    "        max_sum = sum(greater)\n",
    "        nums = [abs(each) for each in nums]\n",
    "        nums = sorted(nums)\n",
    "        del_nums = [0]\n",
    "\n",
    "        for num in nums:\n",
    "            if len(del_nums) < k:\n",
    "                del_nums = del_nums + [each + num for each in del_nums]\n",
    "                del_nums = sorted(del_nums)[:k]\n",
    "            else:\n",
    "                if num >= del_nums[-1]:\n",
    "                    break\n",
    "                del_nums = del_nums + [each + num for each in del_nums]\n",
    "                del_nums = sorted(del_nums)[:k]\n",
    "        return max_sum - del_nums[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]>0): sum += nums[i]\n",
    "            else: nums[i] = -nums[i]\n",
    "        nums.sort()\n",
    "\n",
    "        h = [(0,0)]\n",
    "        for _ in range(k-1):\n",
    "            s, i = heappop(h)\n",
    "            if(i<len(nums)):\n",
    "                heappush(h,(s + nums[i], i+1))\n",
    "                if i: heappush(h, (s + nums[i] - nums[i-1], i+1))\n",
    "        \n",
    "        #s, i = heappop(h)\n",
    "        return sum - h[0][0]\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sums = 0\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            if n > 0:\n",
    "                sums += n\n",
    "            if n < 0:\n",
    "                nums[i] = -n\n",
    "\n",
    "        nums.sort()\n",
    "        # 找出nums第k-1个最小子序列\n",
    "        h = [(-sums, 0)]\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h, (s + nums[i], i + 1))   # 保留nums[i-1]\n",
    "                if i:\n",
    "                    heappush(h, (s + nums[i] - nums[i - 1], i + 1))     # 不保留nums[i-1]\n",
    "\n",
    "        return -h[0][0]\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        s0 = sum(x for x in nums if x > 0)\n",
    "        a = [abs(x) for x in nums]\n",
    "        a = nsmallest(k, a)\n",
    "        a.reverse()\n",
    "        n = len(a)\n",
    "        res = []\n",
    "        s = 0\n",
    "        def dfs(i):\n",
    "            nonlocal s\n",
    "            if i == n:\n",
    "                heappush(res, -s)\n",
    "                if len(res) > k: heappop(res)\n",
    "                return\n",
    "            if len(res) == k and s >= -res[0]: return\n",
    "            dfs(i + 1)\n",
    "            s += a[i]\n",
    "            dfs(i + 1)\n",
    "            s -= a[i]\n",
    "        dfs(0)\n",
    "        return s0 - (-res[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i , x in enumerate(nums):\n",
    "            if x >= 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)] #取负号变成最大堆\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s + nums[i],i+1))\n",
    "                if i:heappush(h,(s + nums[i]-nums[i-1],i+1))\n",
    "        return - h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        def quicksort(_nums:List[int],l,r):\n",
    "            cur,i,j=l,l,r\n",
    "            if i>=j:\n",
    "                return\n",
    "            while i<j:\n",
    "                while i<j and _nums[cur]<_nums[j]:j-=1\n",
    "                while i<j and _nums[cur]>_nums[i]:i+=1\n",
    "                _nums[i],_nums[j]=_nums[j],_nums[i]\n",
    "            _nums[i],_nums[cur]=_nums[cur],_nums[i]\n",
    "            quicksort(_nums,l,i-1)\n",
    "            quicksort(_nums,i+1,r)\n",
    "        _n\n",
    "        quicksort(nums,0,len(nums)-1)\n",
    "        nums=nums[::-1]\n",
    "        print(nums)\n",
    "'''\n",
    "from heapq import heappop,heappush\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: sum += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        #h = [(-sum, 0)]  # 取负号变成最大堆\n",
    "        if k==1:\n",
    "            return sum\n",
    "        else:\n",
    "            h = [(-sum+nums[0], 1)]\n",
    "            for _ in range(1,k-1):\n",
    "                s,i=heappop(h)\n",
    "                if i<len(nums):\n",
    "                    heappush(h,(s+nums[i],i+1))\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        sum  = 0 \n",
    "        for i,x in enumerate(nums):\n",
    "            if x >= 0:\n",
    "                sum += x \n",
    "            else:\n",
    "                nums[i] = -x \n",
    "        nums.sort()\n",
    "\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i: heappush(h,(s+nums[i] - nums[i - 1], i + 1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def kMinSum(arr,k):\n",
    "        n = len(arr)\n",
    "        hp = [(0,0)]\n",
    "        for _ in range(k):\n",
    "            s0,i = heappop(hp)\n",
    "            if i < n and i >= 0:\n",
    "                nxt = arr[i]\n",
    "                nxt_i = i + 1\n",
    "                s1 = s0 + nxt\n",
    "                heappush(hp,(s1,nxt_i))\n",
    "                if i-1 >= 0:\n",
    "                    p = arr[i-1]\n",
    "                    s2 = s1 - p\n",
    "                    heappush(hp,(s2,nxt_i))\n",
    "        return hp[0][0]\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        max_s = sum(x for x in nums if x > 0)\n",
    "        abs_nums = sorted(abs(a) for a in nums)\n",
    "        return max_s - kMinSum(abs_nums,k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0 \n",
    "        for i , x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]>0): sum += nums[i]\n",
    "            else: nums[i] = -nums[i]\n",
    "        nums.sort()\n",
    "\n",
    "        h = [(0,0)]\n",
    "        for _ in range(k):\n",
    "            s, i = heappop(h)\n",
    "            if(i<len(nums)):\n",
    "                heappush(h,(s + nums[i], i+1))\n",
    "                if i: heappush(h, (s + nums[i] - nums[i-1], i+1))\n",
    "        \n",
    "        #s, i = heappop(h)\n",
    "        return sum - s\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i , x in enumerate(nums):\n",
    "            if x > 0 :\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        tot=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x>0: tot +=x\n",
    "            else: nums[i]=-x\n",
    "\n",
    "        nums.sort()\n",
    "        q=[(0,0)]\n",
    "        while k>1:\n",
    "            k -=1\n",
    "           \n",
    "            presum,i=heappop(q)\n",
    "            if i<len(nums):\n",
    "                heappush(q,(presum+nums[i],i+1))\n",
    "                if i: heappush(q,(presum-nums[i-1]+nums[i],i+1))\n",
    "        \n",
    "        return tot-q[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        # sum = 0\n",
    "        # for i, x in enumerate(nums):\n",
    "        #     if x >= 0: sum += x\n",
    "        #     else: nums[i] = -x\n",
    "        # nums.sort()\n",
    "        # h = [(0, 0)]  # 取负号变成最大堆\n",
    "        # for _ in range(k - 1):\n",
    "        #     s, i = heappop(h)\n",
    "        #     if i < len(nums):\n",
    "        #         heappush(h, (s + nums[i], i + 1))  # 保留 nums[i-1]\n",
    "        #         if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1))  # 不保留 nums[i-1]\n",
    "        # return sum-h[0][0]\n",
    "\n",
    "        tot=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x>=0:\n",
    "                tot+=x\n",
    "            else:\n",
    "                nums[i]=-x\n",
    "        nums.sort()\n",
    "        h=[(0,0)]\n",
    "        while k>1:\n",
    "            k-=1\n",
    "            subsum,i = heappop(h)\n",
    "            if i<len(nums):\n",
    "                heappush(h,(subsum+nums[i],i+1))\n",
    "                if i: heappush(h,(subsum+nums[i]-nums[i-1],i+1))\n",
    "        sub_sum,i=heappop(h)\n",
    "        return tot-sub_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i , x in enumerate(nums):\n",
    "            if x >= 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i =heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i : heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0] \n",
    "        # sum = 0\n",
    "        # for i ,x in enumerate(nums):\n",
    "        #     if x >= 0:\n",
    "        #         sum += x\n",
    "        #     else:\n",
    "        #         nums[i] = -x\n",
    "        # nums.sort()\n",
    "        # h = [(-sum,0)]\n",
    "        # for _ in range(k-1):\n",
    "        #     s,i = heappop(h)\n",
    "        #     if i < len(nums):\n",
    "        #         heappush(h,(s+nums[i],i+1))\n",
    "        #         if i: heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        # return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i , x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i , x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                s += nums[i]\n",
    "            else:\n",
    "                nums[i] = -nums[i]\n",
    "        nums.sort()\n",
    "        \n",
    "        heap = [(-s,0)]\n",
    "        for _ in range(k-1):\n",
    "            s, i = heapq.heappop(heap)\n",
    "            if i<n:\n",
    "                heapq.heappush(heap,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heapq.heappush(heap,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -heap[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n= len(nums)\n",
    "        sumN = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0:\n",
    "                sumN += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        heap = [(-sumN, 0)]\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(heap)\n",
    "            if i < n:\n",
    "                heappush(heap, (s + nums[i], i+1))\n",
    "                if i:\n",
    "                    heappush(heap, (s + nums[i] - nums[i - 1], i+1))\n",
    "        return -heap[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: sum += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum, 0)]\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heapq.heappop(h)\n",
    "            if i < len(nums):\n",
    "                heapq.heappush(h, (s + nums[i], i + 1)) \n",
    "                if i: \n",
    "                    heapq.heappush(h, (s + nums[i] - nums[i - 1], i + 1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: sum += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum, 0)]  # 取负号变成最大堆\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h, (s + nums[i], i + 1))  # 保留 nums[i-1]\n",
    "                if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1))  # 不保留 nums[i-1]\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        # temp = [0]\n",
    "        # for n in nums:\n",
    "        #     for nxt in temp[:]:\n",
    "        #         heapq.heappush(temp, n + nxt)\n",
    "        #         while len(temp) > k:\n",
    "        #             heapq.heappop(temp)\n",
    "        #     # print(temp)\n",
    "        # return temp[0]\n",
    "        hq = [(-sum(e for e in nums if e > 0), 0)]\n",
    "\n",
    "        nums = sorted(map(abs, nums))\n",
    "        for _ in range(k-1):\n",
    "            s, i = heapq.heappop(hq)\n",
    "            if i < len(nums):\n",
    "                heappush(hq, (s + nums[i], i + 1))\n",
    "                if i != 0:\n",
    "                    heappush(hq, (s + nums[i] - nums[i-1], i + 1))\n",
    "        return - hq[0][0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            # 如果元素是正数，则加到 sum 中\n",
    "            if x >= 0:\n",
    "                sum += x\n",
    "            # 否则，转换为正数\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        # 对 nums 进行排序，这样 nums[i] 就是第 i 大的数\n",
    "        nums.sort()\n",
    "        # 使用堆来存储可能的最大子序列和\n",
    "        h = [(-sum, 0)]  # 初始化堆\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                # 试图包括 nums[i]\n",
    "                heappush(h, (s + nums[i], i + 1))\n",
    "                if i:\n",
    "                    # 试图不包括 nums[i - 1] 但包括 nums[i]\n",
    "                    heappush(h, (s + nums[i] - nums[i - 1], i + 1))\n",
    "        # 返回第 k 大和\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                s += nums[i]\n",
    "            else:\n",
    "                nums[i] = - nums[i]\n",
    "        nums.sort()\n",
    "        heap = [[- s, 0]]\n",
    "        for _ in range(k):\n",
    "            if not heap:\n",
    "                break \n",
    "            cursum, idx = heapq.heappop(heap)\n",
    "            if idx < n:\n",
    "                heapq.heappush(heap, [ - (- cursum - nums[idx]), idx + 1])\n",
    "                if idx > 0:\n",
    "                    heapq.heappush(heap, [ - (- cursum - nums[idx] + nums[idx - 1]), idx + 1])\n",
    "        return - cursum\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum_=sum(list(filter(lambda x:x>0, nums)))\n",
    "        zeron=len(list(filter(lambda x:x==0, nums)))\n",
    "        if (1<<zeron)>=k: return sum_\n",
    "        k-=(1<<zeron)\n",
    "        nums=list(filter(lambda x:x!=0, nums))\n",
    "        nums=list(map(lambda x:abs(x), nums))\n",
    "        nums.sort()\n",
    "        q=[]\n",
    "        heappush(q, (nums[0], 0))\n",
    "        for _ in range(k):\n",
    "            a,b=heappop(q)\n",
    "            # print(a,b,nums)\n",
    "            if b+1<len(nums):\n",
    "                heappush(q, (a+nums[b+1], b+1))\n",
    "                heappush(q, (a-nums[b]+nums[b+1], b+1))\n",
    "        return sum_-a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum_=sum(list(filter(lambda x:x>0, nums)))\n",
    "        zeron=len(list(filter(lambda x:x==0, nums)))\n",
    "        if (1<<zeron)>=k: return sum_\n",
    "        k-=(1<<zeron)\n",
    "        nums=list(filter(lambda x:x!=0, nums))\n",
    "        nums=list(map(lambda x:abs(x), nums))\n",
    "        nums.sort()\n",
    "        q=[]\n",
    "        heappush(q, (nums[0], 0))\n",
    "        for _ in range(k):\n",
    "            a,b=heappop(q)\n",
    "            # print(a,b,nums)\n",
    "            if b+1<len(nums):\n",
    "                heappush(q, (a+nums[b+1], b+1))\n",
    "                heappush(q, (a-nums[b]+nums[b+1], b+1))\n",
    "        return sum_-a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: sum += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum, 0)]  # 取负号变成最大堆\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h, (s + nums[i], i + 1))  # 保留 nums[i-1]\n",
    "                if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1))  # 不保留 nums[i-1]\n",
    "        return -h[0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: sum += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum, 0)]  # 取负号变成最大堆\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h, (s + nums[i], i + 1))  # 保留 nums[i-1]\n",
    "                if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1))  # 不保留 nums[i-1]\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        total = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 0:\n",
    "                total += nums[i]\n",
    "            else:\n",
    "                nums[i] = -nums[i]\n",
    "        nums.sort()\n",
    "\n",
    "        stack = [[-total, 0]]\n",
    "        while k > 1:\n",
    "            pre, i = heapq.heappop(stack)\n",
    "            pre = -pre\n",
    "            if i < n:\n",
    "                heapq.heappush(stack, [-(pre - nums[i]), i+1])\n",
    "                if i > 0:\n",
    "                    heapq.heappush(stack, [-(pre - nums[i] + nums[i-1]), i+1])\n",
    "            k -= 1\n",
    "\n",
    "        return -heapq.heappop(stack)[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        a=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x>=0:a+=x\n",
    "            else:\n",
    "                nums[i]=-x\n",
    "        nums.sort()\n",
    "        h=[(-a,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i=heappop(h)\n",
    "            if i<len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # numsup = []\n",
    "        # numsdn = []\n",
    "\n",
    "        # for nm in nums:\n",
    "        #     if \n",
    "\n",
    "        # nums.sort()\n",
    "\n",
    "        msum = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                msum += nums[i]\n",
    "            else:\n",
    "                nums[i] = -nums[i]\n",
    "        \n",
    "        nums.sort()\n",
    "\n",
    "        # print(nums)\n",
    "\n",
    "        hp = [(-msum, 0)]\n",
    "\n",
    "        heapq.heapify(hp)\n",
    "\n",
    "        for _ in range(k - 1):\n",
    "\n",
    "            # print(s, i)\n",
    "            \n",
    "            s, i = heapq.heappop(hp)\n",
    "\n",
    "            print(s, i)\n",
    "\n",
    "            if i < len(nums):\n",
    "                heapq.heappush(hp, (s + nums[i], i + 1))\n",
    "                if i:\n",
    "                    heapq.heappush(hp, (s + nums[i] - nums[i - 1], i + 1))\n",
    "        \n",
    "        \n",
    "        return -hp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] =-x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h =[(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: res += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-res, 0)]\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h, (s + nums[i], i + 1))\n",
    "                if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1))\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        s = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= 0:\n",
    "                s += nums[i]\n",
    "            else:\n",
    "                nums[i] = -nums[i]\n",
    "        if n >= k:\n",
    "            nums = heapq.nsmallest(k - 1, nums)\n",
    "        a = [0]\n",
    "        for x in nums:\n",
    "            n = len(a)\n",
    "            m = min(n * 2, k)\n",
    "            b = [0] * m\n",
    "            i1, i2 = 0, 0\n",
    "            for i in range(m):\n",
    "                if i1 < n:\n",
    "                    if a[i1] <= a[i2] + x:\n",
    "                        b[i] = a[i1]\n",
    "                        i1 += 1\n",
    "                    else:\n",
    "                        b[i] = a[i2] + x\n",
    "                        i2 += 1\n",
    "                else:\n",
    "                    b[i] = a[i2] + x\n",
    "                    i2 += 1\n",
    "            a = b\n",
    "        return s - a[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > 0:\n",
    "                sum += x\n",
    "            else:\n",
    "                nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum,0)]\n",
    "        for _ in range(k-1):\n",
    "            s,i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h,(s+nums[i],i+1))\n",
    "                if i:\n",
    "                    heappush(h,(s+nums[i]-nums[i-1],i+1))\n",
    "        return -h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        s = 0\n",
    "        for i, j in enumerate(nums):\n",
    "            if j >= 0:\n",
    "                s += j \n",
    "            else:\n",
    "                nums[i] = -j\n",
    "        nums.sort()\n",
    "        h = [(0, -1)]\n",
    "        for _ in range(k - 1):\n",
    "            sub_s, i = heappop(h)\n",
    "            i += 1\n",
    "            if i < len(nums):\n",
    "                heappush(h, (sub_s + nums[i], i))\n",
    "                if i:\n",
    "                    heappush(h, (sub_s + nums[i] - nums[i - 1], i))\n",
    "        return s - h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        # 先统计所有非负整数的和\n",
    "        s=sum(v for v in nums if v>=0)\n",
    "        nums=[abs(v) for v in nums]\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "\n",
    "        heap=[(-s,0)]\n",
    "        # heapify(heap)\n",
    "        k-=1\n",
    "        while k:\n",
    "            s,i=heappop(heap)\n",
    "            if i<n:\n",
    "                heappush(heap,(s+nums[i],i+1))\n",
    "                if i:heappush(heap,(s+nums[i]-nums[i-1],i+1))\n",
    "            k-=1\n",
    "            print(s)\n",
    "        \n",
    "        return -heap[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sl = []\n",
    "        s = 0\n",
    "        for v in nums:\n",
    "            if v > 0:\n",
    "                s += v\n",
    "                sl.append(-v)\n",
    "            else:\n",
    "                sl.append(v)\n",
    "        \n",
    "        sl = sorted(sl)[::-1]\n",
    "\n",
    "        heap = [(-s, 0)]\n",
    "        \n",
    "        while k > 1:\n",
    "            s, i = heappop(heap)\n",
    "            if i < len(sl):\n",
    "                heappush(heap, (s - sl[i], i+1))\n",
    "                if i > 0:  heappush(heap, (s - sl[i] + sl[i-1], i+1))\n",
    "            k -= 1\n",
    "        \n",
    "        return -heappop(heap)[0]\n",
    "\n",
    "         \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        posSum = zeros = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            if not n:\n",
    "                zeros += 1\n",
    "                continue\n",
    "            if n > 0:\n",
    "                posSum += n\n",
    "                nums[i] = -n\n",
    "        multi = 1<<zeros\n",
    "        if k <= multi: return posSum\n",
    "        remain = k \n",
    "        remain -= multi\n",
    "        nums.sort() \n",
    "        from sortedcontainers import SortedList\n",
    "        h = SortedList()\n",
    "        l = 0\n",
    "        r = len(nums) - 1 - zeros\n",
    "        # print(nums, r, multi)\n",
    "        while True:\n",
    "            l -= 1\n",
    "            if r >= 0 and (-l > len(h) or h[l] < nums[r]): \n",
    "                h.update([x + nums[r] for x in h])\n",
    "                h.add(nums[r])\n",
    "                r -= 1\n",
    "                if len(h) * multi > k:\n",
    "                    h = SortedList(h[-(k+multi-1)//multi:])\n",
    "            if remain <= multi: break\n",
    "            remain -= multi\n",
    "            # print(h, l, r, k, h[ol], nums[r])\n",
    "        # print(l, h)\n",
    "        # print(len(h), l)\n",
    "        return posSum + h[l]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        sum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0: sum += x\n",
    "            else: nums[i] = -x\n",
    "        nums.sort()\n",
    "        h = [(-sum, 0)]  # 取负号变成最大堆\n",
    "        for _ in range(k - 1):\n",
    "            s, i = heappop(h)\n",
    "            if i < len(nums):\n",
    "                heappush(h, (s + nums[i], i + 1))  # 保留 nums[i-1]\n",
    "                if i: heappush(h, (s + nums[i] - nums[i - 1], i + 1))  # 不保留 num[i-1]\n",
    "        print(h)\n",
    "        return -h[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sum_ = sum(i for i in nums if i > 0)\n",
    "        if k == 1:\n",
    "            return sum_\n",
    "        nums = sorted(abs(i) for i in nums)\n",
    "        # 2 ** (m - 1) < k <= 2 ** m\n",
    "        # 二分,对于每个上界x检查nums子序列和 <= x 是否等于k\n",
    "\n",
    "        sl = SortedList([1, 2, 5])\n",
    "        def check(x):\n",
    "            sl = SortedList()\n",
    "            sl.add(0)\n",
    "            for num in nums:\n",
    "                # 找sl中所有小于等于 x - num 的数，然后 + num后再加回去\n",
    "                p = sl.bisect_right(x - num)\n",
    "                for j in list(sl[:p]):\n",
    "                    sl.add(j + num)\n",
    "                    if len(sl) >= k: return False\n",
    "            return True\n",
    "        l, r = 0, sum(nums) \n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return sum_ - l\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sum_ = sum(i for i in nums if i > 0)\n",
    "        if k == 1:\n",
    "            return sum_\n",
    "        nums = sorted(abs(i) for i in nums)\n",
    "        # 2 ** (m - 1) < k <= 2 ** m\n",
    "        # 二分,对于每个上界x检查nums子序列和 <= x 是否等于k\n",
    "\n",
    "        sl = SortedList([1, 2, 5])\n",
    "        def check(x):\n",
    "            sl = SortedList()\n",
    "            sl.add(0)\n",
    "            for num in nums:\n",
    "                # 找sl中所有小于等于 x - num 的数，然后 + num后再加回去\n",
    "                if x - num < 0: return True\n",
    "                p = sl.bisect_right(x - num)\n",
    "                for j in list(sl[:p]):\n",
    "                    sl.add(j + num)\n",
    "                    if len(sl) >= k: return False\n",
    "            return True\n",
    "        l, r = 0, sum(nums) \n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return sum_ - l\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        positive_sum = sum([num for num in nums if num > 0])\n",
    "        nums = sorted([abs(num) for num in nums])\n",
    "        if k == 1:\n",
    "            return positive_sum\n",
    "        \n",
    "        pq, ans_list = [], []\n",
    "        heapq.heappush(pq, (0, -1))\n",
    "\n",
    "        for i in range(k):\n",
    "            term = heapq.heappop(pq)\n",
    "            ans_list.append(term)\n",
    "            v, max_used = term\n",
    "            if max_used + 1 < len(nums):\n",
    "                heapq.heappush(pq, (v + nums[max_used + 1], max_used + 1))\n",
    "                if max_used >= 0:\n",
    "                    heapq.heappush(pq, (v + nums[max_used + 1] - nums[max_used], max_used + 1))\n",
    "        \n",
    "        print(nums)\n",
    "        print(ans_list)\n",
    "        return positive_sum - ans_list[-1][0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        sum_ = sum(i for i in nums if i > 0)\n",
    "        if k == 1:\n",
    "            return sum_\n",
    "        nums = sorted(abs(i) for i in nums)\n",
    "        # 2 ** (m - 1) < k <= 2 ** m\n",
    "        # 二分,对于每个上界x检查nums子序列和 <= x 是否等于k\n",
    "        # (n + klogk)logU\n",
    "        def check(x):\n",
    "            h = [0]\n",
    "            cnt = 1\n",
    "            for num in nums:\n",
    "                # 找sl中所有小于等于 x - num 的数，然后 + num后再加回去\n",
    "                if x - num < 0: return True\n",
    "                tmp = []\n",
    "                while h and h[0] + num <= x:\n",
    "                    tmp.append(heappop(h))\n",
    "                    cnt += 1\n",
    "                    if cnt >= k: return False\n",
    "                for i in tmp:\n",
    "                    heappush(h, i)\n",
    "                    heappush(h, i + num)\n",
    "            return True\n",
    "        l, r = 0, sum(nums) \n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if check(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return sum_ - l\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
